package coalition.formation.partitions;
import java.util.ArrayList;
import java.util.List;


public class Partition {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		Partition testPartition = new Partition(5);
		ArrayList<int[]> partitions = testPartition.getPartitions();
		int counter = 0;
		for(int[] partition: partitions){
			
			//System.out.println(counter + ": " + partitionToString(partition));
			//System.out.println(partitionToExpandedString(partition));
			
			counter ++;
		}
	}
	
	int numElements = -1;
	int[] currentPartition;
	//int maxSetIndex = 0;
	int leftMostModifiablePosition = 0;
	int[] maxValueToLeft;
	
	public Partition(int numElements){
		this.numElements = numElements;
		intialize();
	}
	
	private void intialize(){
		maxValueToLeft = new int[numElements];
		for(int i = 0; i < numElements; i++)
			maxValueToLeft[i] = 0;
	}
	
	private void updateMaxToTheLeft(){
		
		int maxValue = -1;
		for(int i = 0; i < numElements - 1; i++){
			int curValue = currentPartition[i];	
			if(curValue > maxValue){
				maxValue = curValue;
			}
			maxValueToLeft[i + 1] = maxValue;
		}
		
	}
	
	public List<List<List<Integer>>> getPartitionsInListForm(){
		List<List<List<Integer>>> list = new ArrayList<List<List<Integer>>>();
		List<int[]> partitions = getPartitions();
		for(int[] partition : partitions){
			List<List<Integer>> sets = new ArrayList<List<Integer>>();
			for(int i = 0; i < numElements; i++){
				if(sets.size() < partition[i]+ 1)
					sets.add(new ArrayList<Integer>());
				sets.get(partition[i]).add(i);
			}
			list.add(sets);
		}
		
		return list;
	}

	public ArrayList<int[]> getPartitions(){
		int counter = 0;
		ArrayList<int[]> partitions = new ArrayList<int[]>();
		int[] firstPartition = getFirstPartition();
		partitions.add(firstPartition);
		int[] nextPartition = firstPartition;
		currentPartition = nextPartition;
		while(true){
			
			//System.out.println(counter + " maxValues : " + partitionToString(maxValueToLeft));
			System.out.println(" partition " + counter +  ": " + partitionToString(nextPartition));
			//System.out.println(counter + " expanded  : " + partitionToExpandedString(nextPartition));
			counter++;			
			
			updateMaxToTheLeft();
			nextPartition = getNextPartition(nextPartition);
			currentPartition = nextPartition;
			if(nextPartition == null) break;
			else
				partitions.add(nextPartition);
			
		}
		return partitions;
	}
	
	private int[] getFirstPartition(){
		int[] firstPartition = new int[numElements];;
		for(int i = 0; i < firstPartition.length; i++)
			firstPartition[i] = 0;
		return firstPartition;
	}
	
	private int[] getNextPartition(int[] lastPartition){
		int[] nextPartition = copyPartition(lastPartition);
		for(int i = lastPartition.length -1; true;i--){
			if(i == 0 || nextPartition[0] == 1) return null;
			if(nextPartition[i] <= maxValueToLeft[i]){
				//we have no carry from the addition,
				//so we are finished
				nextPartition[i]++; break;
			}
			else {
				
				//we have a carry, so we set the current entry to zero
				//and repeat the process one index position to the left
				nextPartition[i] = 0;
			}
		}
		return nextPartition;
	}
	
	private int[] copyPartition(int[] partition){
		int[] result = new int[numElements];;
		for(int i = 0; i < numElements; i++)
			result[i] = partition[i];
		return result;				
	}
	
	private static String partitionToString(int[] partition){
		StringBuffer result = new StringBuffer("[ ");
		for(int i = 0; i < partition.length; i++){
			if(i != partition.length -1)
				result.append(partition[i] + ", ");
			else
				result.append(partition[i]);
		}
		result.append(" ]");
		return result.toString();
		
	}
	
	private static List<List<Integer>> convertArrayToListForm(int[] partition){
		List<List<Integer>> sets = new ArrayList<List<Integer>>();
		for(int i = 0; i < partition.length; i++){
			if(sets.size() < partition[i]+ 1)
				sets.add(new ArrayList<Integer>());
			sets.get(partition[i]).add(i);
		}
		return sets;
	}
	
	public static String partitionToExpandedString(int[] partition){
		
		List<List<Integer>> sets = convertArrayToListForm(partition);
		
		return partitionListToExpandedString(sets);
		
	}	
	
	private static String partitionListToExpandedString(List<List<Integer>> sets){
		
		StringBuffer result = new StringBuffer("{ ");
		for(int i = 0; i < sets.size(); i++){
			result.append(" {");
			List<Integer> set = sets.get(i);
			for(int j = 0; j < set.size(); j++){
				result.append(set.get(j));
				if(j != set.size() - 1)
					result.append(", ");
			}		
			result.append(" }");
			if(i != sets.size() - 1)
				result.append(", ");
		}
		result.append(" }");
		return result.toString();
		
	}		
	
}
